package org.example.ch04;

import org.example.ch04.tree.ConstructTree;
import org.example.ch04.tree.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 * 给定一个二叉树，找出其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 说明：叶子节点是指没有子节点的节点
 */
public class MinPath {

    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }


    public static void main(String[] args) {

//        TreeNode treeNode = ConstructTree.constructTree(new Integer[]{2,null,3,null,4,null,5,null,6});
        TreeNode treeNode = ConstructTree.constructTree(new Integer[]{2,null,3,null,4,null,5,null,6});
//        int result = minDepth(treeNode);
////        int result = solution1(treeNode);
//        System.out.println(result);

        MinPath minPath = new MinPath();
        System.out.println(minPath.solution1(treeNode));  ;

    }

    public static int minDepth(TreeNode root) {

        //递归的终结条件
        if(root==null){
            return 0;
        }
        if(root.right==null && root.left==null){
            return 1;
        }
        int minDepth = Integer.MAX_VALUE;
        if(root.right!=null){
            int right = minDepth(root.right);
            minDepth = Math.min(minDepth,right);
        }
        if(root.left!=null){
            int left = minDepth(root.left);
            minDepth = Math.min(left,minDepth);
        }

        return minDepth+1;

    }


    public  int solution1(TreeNode root){
        if(root == null){
            return 0;
        }
        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root,1));

        while (!queue.isEmpty()){
            QueueNode queueNode = queue.poll();
            TreeNode node = queueNode.node;
            int depth = queueNode.depth;

            if(node.left==null && node.right==null){
                return depth;
            }
            if(node.left!=null){
                queue.offer(new QueueNode(node.left,depth+1));
            }
            if(node.right!=null){
                queue.offer(new QueueNode(node.right,depth+1));
            }
        }
        return 0;
    }

}
